﻿// Traveling by Stagecoach POJ - 2686  训练营.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://vjudge.net/problem/POJ-2686#author=GPT_zh

从前，有一个旅行者。

他计划乘坐驿站马车旅行。他的起点和目的地是固定的，但他无法确定自己的路线。你在这个问题中的任务是编写一个程序，为他确定路线。

这个国家有几个城市，它们之间有一条连接的道路网络。如果两个城市之间有一条道路，就可以乘坐驿站马车从其中一个城市到另一个城市。乘坐马车需要一张车票，每张车票上都标明了马匹的数量。当然，马匹数量越多，马车就跑得越快。

在起点，旅行者有一些马车票。通过考虑这些车票和道路网络的信息，你应该找到最佳的路线，以最短的时间把他带到目的地。应该考虑车票的使用情况。

假设满足以下条件。
一次马车乘坐可以将旅行者从一个城市直接带到另一个城市。换句话说，每到一个城市，他必须换乘马车。
在两个直接相连的城市之间只能使用一张车票。
每张车票只能使用一次。
马车乘坐所需的时间是两个城市之间的距离除以马匹的数量。
换乘马车所需的时间应该忽略不计。

输入
输入包含多个数据集，每个数据集的格式如下。最后一个数据集后面跟着一行包含五个零（用空格分隔）的数据。

n m p a b
t1 t2 ... tn
x1 y1 z1
x2 y2 z2
...
xp yp zp

数据集中的每个输入项都是非负整数。如果一行包含两个或更多的输入项，则它们之间用空格分隔。

n是马车票的数量。你可以假设车票的数量在1到8之间。m是网络中的城市数量。你可以假设城市的数量在2到30之间。p是城市之间的道路数量，可能为零。

a是起始城市的索引。b是目的地城市的索引。a不等于b。你可以假设数据集中的所有城市索引（包括上述两个）在1到m之间。

数据集的第二行给出了马车票的详细信息。ti是第i张车票上指定的马匹数量（1≤i≤n）。你可以假设马匹数量在1到10之间。

接下来的p行给出了城市之间道路的详细信息。第i条道路连接两个城市，城市索引为xi和yi，距离为zi（1≤i≤p）。你可以假设距离在1到100之间。

没有两条道路连接相同的城市对。一条道路永远不会连接一个城市与自身。每条道路都可以双向行驶。
输出
对于输入中的每个数据集，应输出一行，如下所示。输出行不应包含额外的字符，如空格。

如果旅行者可以到达目的地，则应打印出最佳路线所需的时间（最短时间的路线）。答案不应有大于0.001的误差。你可以输出小数点后的任意位数，只要满足上述精度条件。

如果旅行者无法到达目的地，则应打印字符串“Impossible”。当没有通往目的地的路线时，或者车票数量不足时，都无法到达目的地。请注意，“Impossible”的第一个字母大写，其他字母小写。

3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

30.000
3.667
Impossible
Impossible
2.856

*/

int main()
{
    std::cout << "Hello World!\n";
}

 